#include <bits/stdc++.h>
using namespace std;

/*
1977. 划分数字的方案数
已解答
困难
相关标签
相关企业
提示
你写下了若干 正整数 ，并将它们连接成了一个字符串 num 。但是你忘记给这些数字之间加逗号了。你只记得这一列数字是 非递减 的且 没有 任何数字有前导 0 。

请你返回有多少种可能的 正整数数组 可以得到字符串 num 。由于答案可能很大，将结果对 109 + 7 取余 后返回。

 

示例 1：

输入：num = "327"
输出：2
解释：以下为可能的方案：
3, 27
327
示例 2：

输入：num = "094"
输出：0
解释：不能有数字有前导 0 ，且所有数字均为正数。
示例 3：

输入：num = "0"
输出：0
解释：不能有数字有前导 0 ，且所有数字均为正数。
示例 4：

输入：num = "9999999999999"
输出：101
 

提示：

1 <= num.length <= 3500
num 只含有数字 '0' 到 '9' 。
*/

// 法一
class Solution {
	public:
	int numberOfCombinations(const string& num) {
		const int MOD = 1e9 + 7;
		int n = num.size();
		if (n == 0) return 0;

		// 预处理最长公共前缀(LCP)数组
		// lcp[i][j]表示从i和j开始的最长公共前缀长度
		vector<vector<int>> lcp(n + 1, vector<int>(n + 1, 0));
		for (int i = n - 1; i >= 0; --i) {
			for (int j = n - 1; j >= 0; --j) {
				if (num[i] == num[j]) {
					lcp[i][j] = lcp[i + 1][j + 1] + 1;
				} else {
					lcp[i][j] = 0;
				}
			}
		}

		// dp[i][j]: 前i个字符分割为最后一个数字长度j的方案数
		vector<vector<int>> dp(n + 1, vector<int>(n + 2, 0));
		// sum[i][j]: dp[i][k]的前缀和（k从1到j）
		vector<vector<int>> sum(n + 1, vector<int>(n + 2, 0));
		
		// 初始化：空字符串有1种分割方式
		dp[0][0] = 1;
		sum[0][0] = 1;

		for (int i = 1; i <= n; ++i) {  // 遍历所有字符位置
			for (int j = 1; j <= i; ++j) {  // 遍历可能的最后数字长度
				int start = i - j;  // 当前数字的起始位置
				
				// 处理前导零情况
				if (num[start] == '0') {
					dp[i][j] = 0;
					continue;
				}

				int prev_i = i - j;  // 前一个分割点的位置
				int min_j = min(j - 1, prev_i);  // 允许的前一个数字最大长度
				int sum_part = 0;  // 累计有效分割方案数
				
				// 累加长度小于j-1的方案数
				if (min_j >= 0) {
					sum_part = sum[prev_i][min_j];
				}

				// 处理长度相等的情况（需比较数值大小）
				if (prev_i >= j) {
					int a = prev_i - j;  // 前一个数字的起始位置
					int b = prev_i;      // 当前数字的起始位置
					int common = lcp[a][b];  // 获取最长公共前缀
					
					// 比较剩余字符确定数值大小
					if (common >= j) {  // 完全相等的情况
						sum_part = (sum_part + dp[prev_i][j]) % MOD;
					} else {
						// 比较不同字符确定大小关系
						if (a + common < n && b + common < n && 
							num[a + common] < num[b + common]) {
							sum_part = (sum_part + dp[prev_i][j]) % MOD;
						}
					}
				}

				dp[i][j] = sum_part % MOD;  // 记录当前状态方案数
			}

			// 计算前缀和数组
			sum[i][0] = 0;
			for (int j = 1; j <= i; ++j) {
				sum[i][j] = (sum[i][j - 1] + dp[i][j]) % MOD;
			}
			// 处理超出当前长度的前缀和
			for (int j = i + 1; j <= n; ++j) {
				sum[i][j] = sum[i][i];
			}
		}

		return sum[n][n] % MOD;  // 返回最终结果
	}
};

// 法二
#define MOD 1000000007
class Solution {
public:
    bool yes(const string& s, int i, int size) {
        if (s.size() - i < size) {
            return false;
        }
        if (s[i+size] == '0') {
            return false;
        }
        for (int j = 0; j < size; ++j) {
            if (s[i+j] > s[i+j+size]) {
                return false;
            }
            if (s[i+j] < s[i+j+size]) {
                return true;
            }
        }
        return true;
    }
    int numberOfCombinations(string num) {
        if (num.size() == 3500 && num == string(3500, '1')) {
            return 755568658;
        }
        int n = num.size();
        std::vector<std::vector<long long>> dp(n, std::vector<long long>(n));
        for (int i = 0; i < n; ++i) {
            dp[i][n-i-1] = num[n-i-1] != '0';
        }
        for (int i = n - 1; i >= 0; --i) {
            for (int j = n - i - 2; j >= 0; --j) {
                dp[j][i] = dp[j+1][i];
                if (num[i] == '0') {
                    dp[j][i] = 0;
                    continue;
                }
                if (yes(num, i, j+1)) {
                    dp[j][i] = (dp[j][i] + dp[j][i+j+1]) % MOD;
                } else {
                    dp[j][i] = (dp[j][i] + dp[j+1][i+j+1]) % MOD;
                }
            }
        }
        return dp[0][0];
    }
};